public class Test {
    public ListNode middleNode(ListNode head) {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;

    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null && list2 == null) {
            return null;
        }

        ListNode curA = list1;
        ListNode curB = list2;

        ListNode curN = new ListNode(1);

        ListNode cur = curN;


        while(curA != null && curB != null) {
            if(curA.val < curB.val) {
                cur.next = curA;
                cur = curA;
                curA = curA.next;
            }else {
                cur.next = curB;
                cur = curB;
                curB = curB.next;
            }
        }

        if(curA == null) {
            cur.next = curB;
        }
        if(curB == null) {
            cur.next = curA;
        }
        return curN.next;
    }
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;

        ListNode cur = pHead;

        while(cur != null) {
            if(cur.val < x) {
                //第一次
                if(bs == null) {
                    bs = cur;
                    be = cur;
                }else {
                    be.next = cur;
                    be = cur;
                }
            }else {
                //第一次
                if(as == null) {
                    as = ae = cur;
                }else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }

        if(bs == null) {
            return as;
        }
        if(as == null) {
            return bs;
        }
        ae.next = null;
        be.next =as;
        return bs;
    }
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if(A == null) {
            return false;
        }
        if(A.next == null) {
            return true;
        }

        ListNode fast = A;
        ListNode slow = A;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }

        while(A != slow) {
            if(A.val != slow.val) {
                return false;
            }
            if( A.next == slow) {
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curL = headA;
        ListNode curS = headB;

        int pl = 0;
        int ps = 0;

        while(curL != null) {
            pl++;
            curL =curL.next;
        }

        while(curS != null) {
            ps++;
            curS =curS.next;
        }

        int len = pl - ps;
        curL = headA;
        curS = headB;
        if(len < 0) {
            len = ps - pl;
            curL = headB;
            curS = headA;
        }

        while(len != 0) {
            curL = curL.next;
            len--;
        }

        while(curL != curS) {
            curL = curL.next;
            curS = curS.next;
        }
        if(curL == null) {
            return null;
        }
        return curS;
    }
    public boolean hasCycle(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;

    }
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                while(head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}
